package Lee_code;

public class Lee_684_2 {

    int[] father = new int[1005];

    public int find(int u)
    {
        if(father[u] == u)
            return u;
        father[u] = find(father[u]);
        return father[u];
    }
    public boolean is_same(int u, int v)
    {
        u = find(u);
        v = find(v);
        return u == v;
    }
    //将v添加到u里
    public void join(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v)
            return;
        father[v] = u;
    }

    public int[] findRedundantConnection(int[][] edges) {
        int[] father = new int[1005];
        //初始化father数组
        for(int i: father)
        {
            father[i] = i;
        }

        for (int i = 0; i < edges.length; i++)
        {
            if(is_same(edges[i][0], edges[i][1]))
            {
                return edges[i];
            }
            else {
                join(edges[i][0], edges[i][1]);
            }
        }
        return null;
    }
}
